This invention relates generally to rendering two-dimensional images representing three-dimensional objects, and more particularly, to transforming, sampling, interpolating, and shading in multiple phases.
When rendering three-dimensional objects, two-dimensional images are generated using a computational description of a scene. The description specifies the scene as a collection of three-dimensional objects and associated shader procedures. There are many formats in which individual objects can be represented ranging from a mesh of non-uniform rational B-spline surfaces (NURBS) to an array of independent three-dimensional points. A single description of the scene may utilize many of these formats. However, no matter what format is used, the basic task is to render a two-dimensional output image that represents the scene.
Multiple output images (frames) can be rendered, over time, to form an animated sequence. Usually, there are twenty-four to thirty frames for every second of the animated sequence. Typically, many successive frames in the animated sequence are nearly identical. The background remains relatively constant, while only a small number of objects move with respect to each other, and, perhaps, some objects are added while others are removed.
Further, the viewpoint may change, but typically only by a small amount from one frame to the next.
To take advantage of the similarity of successive frames, the input to the animation system is often specified as an evolving scene description. The evolving scene description is incrementally modified between successive frames to reflect changes in, for example, object position, viewpoint, or the like. The evolving scene description can then be rasterized using image coordinates, and interpolated to generate samples which are shaded by applying the appropriate shader procedures.
A shader is a key element of a three-dimensional renderer. Shading deals with light, shape, material, and texture to determine the appearance of visible surfaces from projective geometry. Because viewers are extremely sensitive to subtleties in shading, the shader must have the flexibility to provide rich images that substantially duplicate the visual reality of the physical world. Because shading can involve complex computations, the shader should also be efficient.
Most prior art rendering systems operate in a single phase. FIG. 1 shows a typical prior art rendering system 100. The system includes a transform, sample, and interpolate (TSI) component 110 and a shader component 120. The TSI receives input in the form of an evolving scene description 101, and control parameters 102, for example, a viewpoint, orientation, size, etc. The scene description 101 includes the geometry (G) defining the shape of the objects in the scene, along with a set of procedural shaders (S) which define how each of the objects will be shaded.
It should be noted that some objects can be composed of other objects. For example, a table object can include one top glass object and four steel leg objects. The table object will generally move and scale as a single unit while different shader procedures are likely to be applied to the top glass object and the steel leg objects.
The output of the TSI are sample points having appearance attributes (A) 103. These attributes include values such as the (x, y, z) position of the sample in shading coordinates and image coordinates, a surface normal, the surface patch parameters (u, v), and the texture coordinates (s, t). The TSI transforms the scene description from object coordinates to image coordinates using the current viewpoint. Rasterization can be used to determine the desired samples, and interpolation is used to generate the appearance attributes for the sample points.
The shader (S) 120 applies the one or more procedural shaders to the appearance attributes of each associated object. The output of the shader 120 is a set of colored samples which can be stored in a frame buffer to generate an image 109. The color of each sample combines, for example, the intrinsic color of the underlying sample, color information from texture maps, diffuse and specular reflections caused by light falling on the object, and other effects.
Additional processing steps (composite and filter) can discard the samples that are hidden by other samples, merge translucent samples with the samples behind them, and calculate pixel values from merged sample values.
For high quality output, samples must be calculated at a finer resolution than the pixel grid and multiple (sub-pixel) samples must then be combined by filtering to generate each pixel.
Traditional single phase rendering has a number of problems. First, the rendering is inefficient. In single phase rendering, the entire scene description is processed by both steps 110 and 120 for each image. Thus, each individual image of the sequence is generated as if it were completely different from every other image in the sequence. If thirty images per second are desired, then all the relevant processing must be done thirty times per second. This is straightforward and robust, but time consuming, particularly for complex scenes.
Furthermore, many prior art traditional single phase rendering systems are limited because they employ classical (non-procedural) texture mapping. However, procedural shading extends this rendering paradigm to provide rich images that duplicate and amplify the visual reality of the physical world. Procedural shading has many advantages over systems limited to classical texture mapping: unrivaled richness and image quality, resolution independence, no seams at boundaries, memory efficient (on demand generation of each shaded sample point), appearance changes (e.g., add some dirt) are easily accommodated, surface distortions are more easily avoided, geometry requirements are reduced, and finally prefiltering is supported which results in superior texture filtering.
U.S. Pat. No. 5,864,342, xe2x80x9cMethod and system for rendering graphical objects to image chunks,xe2x80x9d issued to Kajiya et al. on Jan. 26, 1999, also described by Torborg et al. in xe2x80x9cTalisman: Commodity Realtime 3D Graphics for the PC,xe2x80x9d ACM Siggraph, Conference Proceedings, pp. 353-363, Aug. 4-9, 1996, teaches a rendering system using a polygon geometry.
That system takes a scene description and control information as input to rasterization and shading to generate 32xc3x9732 pixel image xe2x80x9cchunks.xe2x80x9d The chunks are stored in a database. This is done object by object creating chunks in an incremental fashion. Rather than always processing the entire scene description, rapidly changing parts can be processed more often than other parts. This leads to chunk updates that alter the database one chunk at a time.
To generate an image, a full set of chunks is read from the database by an image transformation step, which alters each chunk to partially account for any change in viewpoint. Samples determined from the chunks are sent to a composite and filter step which produces the final image. Due to the intermediate database, chunks can be generated at a slower rate than they are used, concentrating on the chunks that are changing most rapidly. For example, the chunks for an object that is moving in the background can be updated less frequently or with less accuracy than chunks for a foreground object. This makes it possible to generate successive images in an animated sequence without always processing the entire scene for each image.
However, there are many problems with the way chunks are generated and represented that limit their reusability in multiple images, and therefore, limits the benefits of that approach. To start with, all shading is done when chunks are initially generated, and no shading calculations are done when chunks are later used. This allows fast operation, but makes it impossible to adjust a chunk to take proper account of viewpoint sensitive shading effects such as specular reflection. As a result, if the viewpoint changes even a small amount, then the samples generated when reusing a chunk are not the same as those that would be generated if the chunk were recomputed, and image quality suffers. In addition, the chunks are represented as two-dimensional images. This allows fast, space efficient operation, but places strong limits on the way chunks can be transformed.
For the above reasons, the Talisman system either has to process most of the scene description most of the time, or else generate low quality output. The user is faced with either not getting much in the way of efficiency gains, or tolerating bad output. Therefore, it is desired to provide a three-dimensional rendering system that can produce high quality images with reduced processing time.
The invention provides a method and apparatus for rendering an evolving three-dimensional scene description as a series of two-dimensional images (frames). In the method, an evolving scene description includes object geometries G and their associated shader procedures S. Each shader procedure S is factored into a static procedure Ss and a dynamic procedure Sd such that S(A,I)=Sd(Ss(A,R),I), where A denotes the appearance parameters required to shade objects, I denotes an instance of the control parameters, and R denotes a range of control parameters which include I. Similarly, the rendering procedure TSI (transform, sample, and interpolate) for object geometry is factored into a static procedure TSIs and a dynamic procedure TSId such that TSI(G,I)=TSId(TSIs(G,R),I). The factorization of both S and TSI is chosen to significantly reduce the overall rendering time for the evolving scene. Specifically, viewpoint independent or weakly viewpoint dependent computations S5(A,R) and TSIs(G,R) are computed in the static phase of rendering and stored either as independent data structures or as a single combined data structure called the internal representation. This internal representation is then processed by the dynamic phase of rendering to produce each frame.
Since the required dynamic computations to produce a frame are significantly reduced and the required static computations run infrequently, both as a result of a clever factorization and an efficient internal representation, the overall rendering time is reduced.
In one aspect of the invention, only the factorization of the shading procedure S is performed. The static and dynamic phases perform the shading computations as described above. A data structure, called shader maps, is used to store the results of the static shading computations, and the globally reparameterized input geometry is used in the dynamic phase.
In another aspect of the invention, both the factorization of S and TSI is performed. The static and dynamic phases perform both the shading and geometry computations as described above, and a single combined data structure is used to store both the results of the static shading computations and the static geometry computations.
In another aspect of the invention, both the factorization of S and TSI is performed, the static and dynamic phases perform both the shading and geometry computations as described above, and separate data structures are used to store the results of the static shading computations and the static geometry computations. The static shading computations are stored in shader maps.
In another aspect of the invention, the range of control parameters includes a range of viewpoints, and the instance of control parameters includes a particular viewpoint, and the static shader is either independent of the particular viewpoint or weakly dependent on the particular viewpoint.
In another aspect of the invention, the intermediate representation is expressed using an object coordinate system.
The intermediate representation can include a mesh of polygons having vertices connected by edges (called polygonal facets), or, alternatively, the intermediate representation can include shader maps. Both polygonal facets and shader maps are described below.